package algorithm.kmp;

import java.util.ArrayList;
import java.util.List;

public class KMP {

    //最长前后缀串匹配长度的作用为：1、找到一种可能当出现不匹配字符时，进行匹配的串成功的位置；
    //                 2、只要这个最长前缀是最长的，原开始位置到新开始位置就不可能是有效的
    //
    // 最长前后缀： 不走一些路（最长的前后缀相等长度），少走一些路，利用前面走过的路（前缀后缀相等的部分）
    //
    //整体思路：被匹配的长字符串与短串字符匹配时只需向前遍历即可，在遍历的过程中进行两个串的字符比较，
    //         当出现不一样的时候（在长串中点a与短串中b不一样）就要开始调整短串与长串进行比较的位置了，
    //         只需要将a点与短串中的next[b]值对应的点对上进行比较，因为短串中next[b]值对应的点之前的字符与长串就自动匹配上了。
    //         当next[b]的值为-1时两串对应点还不能匹配上，则长串向前进一位。
    //时间复杂度O（2N）即O（N），最复杂的情况：开始两串都匹配上了，直到最后一位匹配失败，而短串在调整位置时也是从后往前一个一个比较。


    //求解过程中定义两个变量指向两个字符串处理过程中的位置
    public static int getIndexOf(String s1, String s2){
        if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
            return -1;
        }
        int[] next = getNextArray(s2.toCharArray());
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int x = 0;
        int y = 0;
        while(x < str1.length && y < str2.length){
            if(str1[x] == str2[y]){
                x++;
                y++;
            }else if(next[y] == -1){//表示第一个位置都不相等
                x++;
            }else {
                y = next[y];
            }
        }
        return y == str2.length ? x - y : -1;
    }


    public static int[] getNextArray(char[] str2){
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;
        for (int i = 2; i < str2.length; i++) {
            int left = next[i - 1];
            while(left >= 0){
                if(str2[left] == str2[i - 1]){
                    next[i] = left + 1;
                    break;
                }
                else
                    left = next[left];
            }
        }
        return next;
    }

    public static List<Integer> getMuiIndexOf(String s1, String s2){
        if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
            return null;
        }
        int[] next = getNextArray2(s2.toCharArray());
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        ArrayList<Integer> res = new ArrayList<>();
        int x = 0;
        int y = 0;
        while(x < str1.length){
            if(y != str2.length && str1[x] == str2[y]){
                x++;
                y++;
                if(y == str2.length)
                    res.add(x - y);
            }else if(next[y] == -1){
                x++;
            }else {
                y = next[y];
            }
        }
        return res;
    }

    public static int[] getNextArray2(char[] str2){
        int[] next = new int[str2.length + 1];
        next[0] = -1;
        next[1] = 0;
        for (int i = 2; i <= str2.length; i++) {
            int left = next[i - 1];
            while(left >= 0){
                if(str2[left] == str2[i - 1]){
                    next[i] = left + 1;
                    break;
                }
                else
                    left = next[left];
            }
        }
        return next;
    }

    public static void main(String[] args) {
//        int[] nextArray = getNextArray(new char[]{'a', 'b', 'c', 'a', 'b', 'c'});
//        for (int i = 0; i < nextArray.length; i++) {
//            System.out.println(nextArray[i]);
//        }

        List<Integer> list = getMuiIndexOf("cabcrtyabcabc", "abc");
        System.out.println(list);
    }

}
